翻訳と辞書 Words near each other ・ Sauerbrunn (surname) ・ Sauerkraut ・ Sauerkraut (Helme Heine) ・ Sauerkraut candy ・ Sauerkraut Days ・ Sauerlach ・ Sauerland ・ Sauerland (surname) ・ Sauerland Net ・ Sauerland-Express ・ Sauerländer Heimatbund ・ Sauerländischer Gebirgsverein ・ Sauermugg ・ Sauers ・ Sauerthal ・ Sauer–Shelah lemma ・ Sauf si l'amour... ・ Saufatu Sopoanga ・ Saufley ・ Saufley Field ・ Saug-a-Gaw-Sing 1, Ontario ・ Sauga ・ Sauga Parish ・ Sauga River ・ Sauganash Historic District ・ Sauganash Hotel ・ Saugandh ・ Saugandh (1991 film) ・ Saugandh Ganga Maiya Ke ・ Saugat Malla Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Sauer–Shelah lemma ： ウィキペディア英語版 Sauer–Shelah lemma In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it independently of each other in 1972.〔.〕〔.〕 The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named.〔.〕 In his paper containing the lemma, Shelah gives credit also to Micha Perles, and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma.〔.〕 Buzaglo et al. call this lemma "one of the most fundamental results on VC-dimension",〔 and it has applications in many areas. Sauer's motivation was in the combinatorics of set systems, while Shelah's was in model theory and that of Vapnik and Chervonenkis was in statistics. It has also been applied in discrete geometry〔.〕 and graph theory.〔.〕 ==Definitions and statement== If $\backslash mathcal=\backslash$ is a family of sets, and $T$ is another set, then $T$ is said to be shattered by $\backslash mathcal$ if every subset of $T$ (including the empty set and $T$ itself) can be obtained as an intersection $T\backslash cap\; S\_i$ between $T$ and a set in the family. The VC dimension of $\backslash mathcal$ is the largest cardinality of a set shattered by $\backslash mathcal$. In terms of these definitions, the Sauer–Shelah lemma states that if $\backslash mathcal$ is a family of sets with $n$ distinct elements such that $|\backslash mathcal|\; >\; \backslash sum\_^\; \}$, then $\backslash mathcal$ shatters a set of size $k$. Equivalently, if the VC dimension of $\backslash mathcal$ is $k$, then $\backslash mathcal$ can consist of at most $\backslash sum\_^\; \}\; =O(n^k)$ sets. The bound of the lemma is tight: there exists a family $\backslash mathcal$ with $|\backslash mathcal|\; =\; \backslash sum\_^\; \}$ that does not shatter any set of size $k$. Namely, let $\backslash mathcal$ be the family of all subsets of $\backslash$ that have cardinality less than $k$.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sauer–Shelah lemma」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.